package com.tgy.algorithm.base._递归;

import java.util.Map;

public class _背包问题_递归 {

    /**
     * 给定两个长度都为N的数组weights和values, weights[]和values[]分别代表 i号物品的重量和价值。
     * 给定一个正数bag，表示一个载重bag的袋子你装的物品不能超过这个重量。
     * 返回你能装下最多的价值是多少?
     * @param args
     */

    public static int getMaxBackPack(int[] weights,int[] values,int bag) {

//        return doGetMaxBackpack(weights,values,0,0,bag);
        return doGetMaxBackpack01(weights,values,0,bag);
    }


    public static int doGetMaxBackpack(int[] weights,int[] values,int index,int weighted,int bag) {

        if (index >= weights.length) {
            // 本次商品越界了，直接返回价值为0
            return 0;
        }

        // 不装当前index位置的物品
        int value = doGetMaxBackpack(weights,values,index+1,weighted,bag);

        // 装当前index位置的物品
        int ownValue;
        int nextWeighed = weighted + weights[index];
        if (nextWeighed <= bag) {
            ownValue = doGetMaxBackpack(weights, values, index + 1, nextWeighed, bag) + values[index] ;
        }else {
            ownValue = 0;
        }

        System.out.println("value:"+value + " ownValue" + ownValue);
        return Math.max(value,ownValue);
    }


    public static int doGetMaxBackpack01(int[] weights,int[] values,int index,int residue) {

        if (index >= weights.length) {
            return 0;
        }

        int notingValue = doGetMaxBackpack01(weights, values, index+1, residue);

        int obtainValue = 0;
        int residueWeights = residue - weights[index];
        if (residueWeights >= 0) {
            obtainValue = doGetMaxBackpack01(weights,values,index+1,residueWeights) + values[index];
        }

        return Math.max(notingValue,obtainValue);
    }

    public static void main(String[] args) {
        int[] weights = {2,3,5,7};
        int[] values = {1,5,2,4};
        int ma = getMaxBackPack(weights, values, 10);
        System.out.println(ma);
    }
}
